Karush-Kuhn-Tucker (KKT) conditions

Consider a general primal optimization problem (no assumptions of convexity or differentiability).

Then KKT conditions are

1. stationary, i.e. $0 \in \partial \left(L(x,\lambda, \nu)\right)$
   • i.e. $\nabla f_0 (x^*) + \sum_{i=1}^n \lambda_i^* \nabla f_i(x^*) A^T \nu^* = 0$
2. complementary slackness, i.e.
3. primal feasibility,
   • i.e. $f_i(x^*) \leq 0$
4. dual feasibility, i.e.

#incomplete

Also see: Slater condition

References:

• https://www.cs.cmu.edu/~pradeepr/convexopt/Lecture_Slides/dual-ascent.pdf